import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * 18. 四数之和
 * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
 * <p>
 * 注意：
 * <p>
 * 答案中不可以包含重复的四元组。
 * <p>
 * 示例：
 * <p>
 * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 * <p>
 * 满足要求的四元组集合为：
 * [
 * [-1,  0, 0, 1],
 * [-2, -1, 1, 2],
 * [-2,  0, 0, 2]
 * ]
 */

class Solution {

    public static void main(String[] args) {
        List<List<Integer>> all = fourSum(new int[]{1, -5, -5, -3, 2, 5, 0, 4}, -7);
        System.out.println(all.size());
    }

    /**
     * 定下第一个点a之后，寻找可能能找到答案的d，再双指针去找bc
     *
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        return new ArrayList<>();
    }

    /**
     * 使用set去重
     *
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> fourSum1(int[] nums, int target) {
        List<List<Integer>> all = new ArrayList<>();
        HashSet<String> set = new HashSet<>();
        Arrays.sort(nums);
        int preSum, tmpSum, allSum;
        List<Integer> tmp;
        Integer[] res;
        String x;
        for (int a = 0; a < nums.length - 3; a++) {
            preSum = nums[a] + nums[a + 1] + nums[a + 2];
            for (int d = nums.length - 1; d >= a + 3; d--) {
                allSum = preSum + nums[d];
                if (allSum < target) {
                    // 当a+b有可能存在解时，遍历出bc
                    tmpSum = nums[a] + nums[d];
                    for (int b = a + 1, c = d - 1; b < c; ) {
                        allSum = tmpSum + nums[b] + nums[c];
                        if (allSum == target) {
                            res = new Integer[]{nums[a], nums[b], nums[c], nums[d]};
                            x = Arrays.toString(res);
                            if (!set.contains(x)) {
                                set.add(x);
                                tmp = Arrays.asList(res);
                                all.add(tmp);
                            }
                            b++;
                            c--;
                        } else if (allSum < target) {
                            b++;
                        } else {
                            c--;
                        }
                    }
                } else if (allSum == target) {
                    res = new Integer[]{nums[a], nums[a + 1], nums[a + 2], nums[d]};
                    x = Arrays.toString(res);
                    if (!set.contains(x)) {
                        set.add(x);
                        tmp = Arrays.asList(res);
                        all.add(tmp);
                    }
                }
            }
        }
        return all;
    }

    /**
     * 使用跳过重复数据去重
     *
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> fourSum2(int[] nums, int target) {
        List<List<Integer>> all = new ArrayList<>();
        Arrays.sort(nums);
        int preSum, tmpSum, allSum;
        List<Integer> tmp;
        Integer[] res;
        String x;
        for (int a = 0; a < nums.length - 3; ) {
            preSum = nums[a] + nums[a + 1] + nums[a + 2];
            for (int d = nums.length - 1; d >= a + 3; ) {
                allSum = preSum + nums[d];
                if (allSum < target) {
                    // 当a+b有可能存在解时，遍历出bc
                    tmpSum = nums[a] + nums[d];
                    for (int b = a + 1, c = d - 1; b < c; ) {
                        allSum = tmpSum + nums[b] + nums[c];
                        if (allSum == target) {
                            tmp = Arrays.asList(nums[a], nums[b], nums[c], nums[d]);
                            all.add(tmp);
                            while (b < c && nums[b] == nums[++b]) {
                            }
                            while (b < c && nums[c] == nums[--c]) {
                            }
                        } else if (allSum < target) {
                            while (b < d && nums[b] == nums[++b]) {
                            }
                        } else {
                            while (b < c && nums[c] == nums[--c]) {
                            }
                        }
                    }
                } else if (allSum == target) {
                    tmp = Arrays.asList(nums[a], nums[a + 1], nums[a + 2], nums[d]);
                    all.add(tmp);
                }
                while (d >= a + 3 && nums[d] == nums[--d]) {
                }
            }
            while (a < nums.length - 3 && nums[a] == nums[++a]) {
            }
        }
        return all;
    }

}